//
// Created by Administrator on 2021/5/25.
//

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

//Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode *constructMaximumBinaryTree(vector<int> &nums) {
        auto ans = helper(nums, 0, (int)nums.size());
        return ans;
    }

    TreeNode *helper(vector<int> &nums, int left, int right) {
        if (left >=  right) return nullptr;
        // 最大的元素在数组中的下标
        auto maxPt = max_element(nums.begin()+left, nums.begin()+right);
        int maxNumIndex = maxPt - nums.begin();
        // 建立节点
        auto root = new TreeNode(*maxPt);
        // 建立左右节点
        root->left = helper(nums,left,maxNumIndex);
        root->right = helper(nums,maxNumIndex+1,right);
        // 返回该节点
        return root;
    }

    vector<int> inorderTraversal(TreeNode *root) { // 中序遍历
        vector<int> ans;
        inorder(root, ans);
        return ans;
    }

    void inorder(TreeNode *t, vector<int> &v) { // 递归函数
        if (t == nullptr) {
            return;
        }
        inorder(t->left, v);
        v.push_back(t->val);
        inorder(t->right, v);
    }
};

int main() {
    vector<int> v{3, 2, 1, 6, 0, 5};
    Solution sol;
    auto root = sol.constructMaximumBinaryTree(v);
    auto ans = sol.inorderTraversal(root);
    for (auto &x:ans) cout << x << endl;
    return 0;
}